#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> res;
        string temp;
        dfs(n, 0, 0, temp, res);
        return res;
    }
    // 思路： 使用深度优先搜索（DFS）来生成所有可能的括号组合。
    // 具体做法是维护两个计数器，left和right，分别表示当前生成的左括号和右括号的数量。
    // 1. 当left小于n时，可以添加一个左括号。
    // 2. 当right小于left时，可以添加一个右括号。
    // 3. 当left和right都等于n时，说明生成了一个合法的括号组合，将其加入结果集。
    // 4. 通过回溯的方式，探索所有可能的组合。
    void dfs(int n, int left, int right, string &temp, vector<string> &res)
    {
        if (left == n && right == n) // 找到一个合法的括号组合
        {
            res.push_back(temp);
            return;
        }
        if (left < n) // 可以添加左括号 为什么是left < n？ 因为左括号的数量不能超过n
        {
            temp.push_back('(');
            dfs(n, left + 1, right, temp, res);
            temp.pop_back();
        }
        if (right < left) // 可以添加右括号 为什么不是right < n？ 因为右括号的数量不能超过左括号的数量
        {
            temp.push_back(')');
            dfs(n, left, right + 1, temp, res);
            temp.pop_back();
        }
    }
};